1511D - Min Cost String - CodeForces Solution


brute force constructive algorithms graphs greedy strings *1600

Please click on ads to support us..

Python Code:

from sys import stdin
from collections import defaultdict
import string
input = stdin.readline

class Solution:
    def dfs(self, u):
        while self.G[u]:
            v = self.G[u].pop()
            self.dfs(v)
        self.tour.append(u)

    def find_tour(self):
        self.n, self.k = map(int, input().split())
        letters = string.ascii_lowercase[:self.k]; self.tour = []

        self.G = defaultdict(list)
        for l1 in letters:
            for l2 in letters:
                self.G[l1].append(l2)

        self.dfs('a')
        self.tour.pop()

        ans = []
        for i in range(self.n):
            ans.append(self.tour[i % len(self.tour)])

        print(''.join(ans))


solution_obj = Solution()
solution_obj.find_tour()


        






C++ Code:

#include <bits/stdc++.h>
#include <unordered_set>
#include <iostream>
#include <string>
using namespace std;


typedef long long int ll;
const int mod = 1e9 + 7;
#define INF 1e9
#define CLR(a) memset(a, 0, sizeof(a))
#define SET(a, val) memset(a, val, sizeof(a))


#define N 200005
void solve(int round)
{
    int n, k;
    int last = 0;
    string s = "";

    cin >> n >> k;

    while (s.size() < n) {
        for (int j1 = 0; (j1 < k) && (s.size() < n); j1++) {
            s += ('a' + j1);
            for (int j2 = j1+1; (j2 < k) && (s.size() < n); j2++) {
                s += ('a' + j1);
                s += ('a' + j2);
            }
        }
    }
    if (s.size() > n) {
        s.pop_back();
    }
    
    printf("%s\n", s.c_str());
}

int main()
{
#if 1
    std::ifstream in("C:\\Users\\user\\source\\repos\\ConsoleApplication1\\ConsoleApplication1\\test.txt", ::std::ios::binary);
    std::streambuf* cinbuf = std::cin.rdbuf();//save old buf
    std::cin.rdbuf(in.rdbuf());//redirect std::cin to in.txt!
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    int round = 1;
    //cin >> tc;
    while (tc--) {
        solve(round);
        round++;
    }
    return 0;

}


Comments

Submit
0 Comments
More Questions

1430B - Barrels
279B - Books
1374B - Multiply by 2 divide by 6
1093B - Letters Rearranging
1213C - Book Reading
1468C - Berpizza
1546B - AquaMoon and Stolen String
1353C - Board Moves
902A - Visiting a Friend
299B - Ksusha the Squirrel
1647D - Madoka and the Best School in Russia
1208A - XORinacci
1539B - Love Song
22B - Bargaining Table
1490B - Balanced Remainders
264A - Escape from Stones
1506A - Strange Table
456A - Laptops
855B - Marvolo Gaunt's Ring
1454A - Special Permutation
1359A - Berland Poker
459A - Pashmak and Garden
1327B - Princesses and Princes
1450F - The Struggling Contestant
1399B - Gifts Fixing
1138A - Sushi for Two
982C - Cut 'em all
931A - Friends Meeting
1594A - Consecutive Sum Riddle
1466A - Bovine Dilemma